package com.algorithm.binarytree;
/*
 *@Author:DOWN
 *@Date:2022/2/9 14:51
 *@Comment: 前 中 后 表示何时访问该节点
    例如： 12  15 28
        前  15 12 28
        中  12 15 28
        后  12 28 15
 */

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Main<E extends Comparable<E>> {
    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public Main() {
        root = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    //优化后----------------
    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        return node;
    }

    /**
     * 包含查询
     *
     * @param e 元素
     * @return boolean 是否包含
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    /**
     * 包含查询实现
     *
     * @param node 上级节点
     * @param e    查询元素
     * @return boolean
     */
    private boolean contains(Node node, E e) {
        //空 结束
        if (node == null) {
            return false;
        }
        //查询成功
        if (e.compareTo(node.e) == 0) {
            return true;
        }
        //往左节点 查询
        else if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        }
        //往右节点 查询
        else {
            return contains(node.right, e);
        }
    }

    //优化前----------------
    public void addOld(E e) {
        if (root == null) {
            root = new Node(e);
            size++;
        } else {
            addOld(root, e);
        }
    }

    private void addOld(Node node, E e) {
        //重复跳过
        //new Node(e) 挂在新的叶子节点 ， 看作叶子节点 下 还存在两个 值为null 的子节点，方便理解。
        if (e.equals(node.e)) {
            return;
        } else if (e.compareTo(node.e) < 0 && node.left == null) {
            node.left = new Node(e);
            size++;
            return;
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            node.right = new Node(e);
            size++;
            return;
        }
        //进入递归算法 重复向下层节点 寻找 正确的叶子位置
        if (e.compareTo(node.e) < 0) {
            addOld(node.left, e);
        } else {
            addOld(node.right, e);
        }
    }

    // 向二分搜索树中添加新的元素e，     非递归写法
    //关键是找 需要插入的空节点
    public void add2(E e) {

        // 对二分搜索树是空的情况特殊处理
        // 此时，直接让 root 指向新的节点即可
        if (root == null) {
            root = new Node(e);
            size++;
            return;
        }

        // 用 p 来跟踪待插入节点的上一个节点
        // p 的作用相当于链表插入节点时，pre 的作用
        Node p = root;
        while (true) {

            // 如果待插入的值小于当前 p 节点的值
            // 说明新插入的值要放在 p 的左子树
            if (e.compareTo(p.e) < 0) {
                // 如果 p 的左子树为空，则在 p.left 上放入新的节点
                if (p.left == null) {
                    p.left = new Node(e);
                    size++;
                    return; // 注意这里直接 return
                }

                // 否则 p = p.left
                p = p.left;
            }
            // 如果待插入的值大于当前 p 节点的值
            // 说明新插入的值要放在 p 的右子树
            else if (e.compareTo(p.e) > 0) {
                // 如果 p 的右子树为空，则在 p.right 上放入新的节点
                if (p.right == null) {
                    p.right = new Node(e);
                    size++;
                    return; // 注意这里直接 return
                }

                // 否则 p = p.right
                p = p.right;
            }
            // 如果待插入的值等于当前 p 节点的值，说明二分搜索树中已经有这个值了
            // 直接 return
            else {
                return;
            }
        }
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 前序遍历-非递归
     */
    public void preOrderNR() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.e);

            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

    /**
     * 层序遍历
     */
    public void levelOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node cur = q.remove();
            System.out.println(cur.e);

            if (cur.left != null) {
                q.add(cur.left);
            }
            if (cur.right != null) {
                q.add(cur.right);
            }
        }
    }

    /**
     * 查找最小 元素
     *
     * @return E
     */
    public E minItem() {
        if (size == 0) {
            throw new IllegalArgumentException("The three is null ！");
        }
        return minItem(root).e;
    }

    private Node minItem(Node node) {
        if (node.left == null) {
            return node;
        }
        return minItem(node.left);
    }

    /**
     * 删除最小节点 返回最小节点
     *
     * @return E
     */
    public E removeMin() {
        //查询待返回的最小值
        E ret = minItem();
        //获取 删除最小值后的 新的根节点
        root = removeMin(root);
        return ret;
    }

    /**
     * 删除最小值节点
     * 返回新的根节点
     *
     * @param node 节点
     * @return Node 删除的节点
     */
    private Node removeMin(Node node) {
        if (node.left == null) {
            //预存 最小值的右节点
            Node rightNode = node.right;
            //删除最小值的右节点
            node.right = null;
            //元素 个数 --
            size--;
            //返回新的 节点
            return rightNode;
        }
        //递归至 最小值的节点
        node.left = removeMin(node.left);
        return node;
    }

    /**
     * 删除最大节点 返回最大节点
     *
     * @return E
     */
    public E removeMax() {
        //查询待返回的最大值
        E ret = maxItem();
        //获取 删除最小值后的 新的根节点
        root = removeMax(root);
        return ret;
    }

    /**
     * 删除最小值节点
     * 返回新的根节点
     *
     * @param node 节点
     * @return 已删除的节点
     */
    private Node removeMax(Node node) {
        if (node.right == null) {
            //预存 最大值的左节点
            Node leftNode = node.left;
            //删除最大值的左节点
            node.left = null;
            //元素 个数 --
            size--;
            //返回新的 节点
            return leftNode;
        }
        //递归至 最大值的节点
        node.right = removeMax(node.right);
        return node;
    }

    /**
     * 查找最大 元素
     *
     * @return E
     */
    public E maxItem() {
        if (size == 0) {
            throw new IllegalArgumentException("The three is null ！");
        }
        return maxItem(root).e;
    }

    private Node maxItem(Node node) {
        if (node.right == null) {
            return node;
        }
        return maxItem(node.right);
    }

    /**
     * 删除任意节点
     *
     * @param e 元素
     */
    public void remove(E e) {
        root = remove(root, e);
    }

    /**
     * 删除任意节点  方法实现
     *
     * @param node 元素
     * @param e    要删除的节点
     * @return 新的节点
     */
    private Node remove(Node node, E e) {
        //空 则 结束
        if (node == null) {
            return null;
        }
        //往 左 节点递归
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        }
        //往 右 节点递归
        else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else { //node.e == e
            //左节点为空
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            //右节点为空
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //左右节点 都不为空
            //获取 右节点的最小值 作为 后续节点
            Node item = minItem(node.right);
            //后续节点 获取 原左节点
            item.left = node.left;
            //后续节点 获取 不含本身的右节点
            item.right = removeMin(node.right);
            //原节点 清除
            node.left = node.right = null;
            //返回新的 后继节点
            return item;
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateString(root, 0, res);
        return res.toString();
    }

    private void generateString(Node node, int depth, StringBuilder res) {
        if (node == null) {
            res.append(GenerateDepthString(depth)).append("null\n");
            return;
        }
        res.append(GenerateDepthString(depth)).append(node.e).append("\n");
        generateString(node.left, depth + 1, res);
        generateString(node.right, depth + 1, res);
    }

    private String GenerateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        res.append("--".repeat(Math.max(0, depth)));
        return res.toString();
    }

}
